package algorithm.bin_tree;

import java.util.*;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * @program: util
 * @description: 二叉树层序遍历
 * 广度遍历使用队列
 * @author: zhouliangliang
 * @create: 2021-06-03 20:54
 **/
public class LayerTraverse {

    /**
     * 层序遍历
     * 使用队列
     * @param
     */
    private void layerTraverse(Node root) {
        Queue<Node> queue = new ArrayDeque<>();
        //头结点入队列
        queue.add(root);

        while (!queue.isEmpty()) {
            //头结点出队列
            Node node = queue.poll();

            if(node == null) {
                continue;
            }

            if(node != null && node.leftChild != null) {
                queue.add(node.leftChild);
            }

            if(node != null && node.rightChild != null) {
                queue.add(node.rightChild);
            }
            System.out.print(node.data + " ");
        }
    }

    /**
     * 层序遍历，并输出每一层
     * 思路: 把每一层的元素用一个新的队列记录起来
     * @param root
     */
    private void layerTraverseElement(Node root) {
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(root);
        analysis(queue);
        while (!queue.isEmpty()) {
            Queue<Node> newQueue = new ArrayDeque<>();
            queue = loopQueue(queue, newQueue);
            analysis(queue);
        }
    }

    private Queue<Node> loopQueue(Queue<Node> queue, Queue<Node> newQueue) {
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if(node == null) {
                continue;
            }

            if(node.leftChild != null) {
                newQueue.add(node.leftChild);
            }
            if(node.rightChild != null) {
                newQueue.add(node.rightChild);
            }
        }
        return newQueue;
    }

    private void analysis(Queue<Node> queue) {
        if(queue.isEmpty()) {
            return;
        }
        String layerData = queue.stream().map(node->{
            return String.valueOf(node.data);
        }).reduce((a,b)->{return a + ", " + b;}).orElseGet(null);

        int index = layerData.lastIndexOf(",");

        System.out.println("layerData : " + layerData + " lastData: " + layerData.substring( index == -1 ? 0: index+1));
    }

}
